ipair a[200010];
int p[200010],rank[200010],SA[200010],lcp[200010],L[200010],R[200010],ans[200010],K,n,st[200010],m;
char S[200010];
int in[200010],out[200010],nxt[200010],s[200010],cnt[200010],q[200010],rp[200010],ss[200010],rq[200010];

void DA()
{
	int i,o;
	memcpy(ss,s,sizeof ss);
	sort(ss+1,ss+n+1);
	for(i=1;i<=n;i++) rank[i]=lower_bound(ss+1,ss+n+1,s[i])-ss;
	for(o=1;o<=n;o<<=1)
	{
		for(i=1;i+o<=n;i++) a[i]=mp(rank[i],rank[i+o]);
		for(;i<=n;i++) a[i]=mp(rank[i],0);
		memset(cnt,0,sizeof cnt);
		for(i=n;i;i--) cnt[a[i].se]++;
		for(i=1;i<=n;i++) cnt[i]+=cnt[i-1];
		for(i=n;i;i--) rp[p[i]=cnt[a[i].se]--]=i;
		memset(cnt,0,sizeof cnt);
		for(i=n;i;i--) cnt[a[i].fi]++;
		for(i=1;i<=n;i++) cnt[i]+=cnt[i-1];
		for(i=n;i;i--) rq[q[rp[i]]=cnt[a[rp[i]].fi]--]=rp[i];
		rank[rq[1]]=1;
		for(i=2;i<=n;i++) if (a[rq[i]]==a[rq[i-1]]) rank[rq[i]]=rank[rq[i-1]]; else rank[rq[i]]=i;
	}
	for(i=1;i<=n;i++) SA[rank[i]]=i;
	// calc lcp
	for(i=1;i<=n;i++)
		for(lcp[rank[i]]=max(lcp[rank[i-1]]-1,0);s[i+lcp[rank[i]]]==s[SA[rank[i]+1]+lcp[rank[i]]];lcp[rank[i]]++);
}